package com.algorithm.learning.binarysearch;

/**
 * @program: algorithm-learning
 * @description:
 * @author: YuKai Fan
 * @create: 2024/8/16 21:15
 **/
public class 寻找旋转排序数组中的最小值 {

    /**
     * 这个题目的意思是
     * 给一个数组，这个数组原本是升序的
     * 但是旋转了几次之后得到了一个无序数组，找到这个无序数组的最小值
     * 例如：数组为[3,4,5,1,2]，因为原数组[1,2,3,4,5]经过3次旋转之后，可以得到此数组，那么第一个元素就是最小值
     * 怎么旋转呢? 解释如下
     * 原数组为[1,2,3,4,5]，此时把5放在最前面，那么数组为[5,1,2,3,4]，即为旋转1次
     * 再把4放在最前面，数组为[4,5,1,2,3]，即为旋转2次
     * 再把3放在最前面，数组为[3,4,5,1,2]，即为旋转3次
     *
     * 所以按照这个思路，我们
     * @param nums
     * @return
     */
    public static int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            // 这里mid值小于右边，说明[mid, right] 是一个上升区间，那么最小值肯定不在[mid + 1, right], 直接可以舍弃，只需要判断[left, mid]即可
            if (nums[mid] < nums[right]) {
                right = mid;
            } else if (nums[mid] == nums[right]) {
                // 这里判断是否存在重复元素的情况
                right = right - 1;
            } else {
                left = mid + 1;
            }
        }
        return nums[left];
    }

    public static void main(String[] args) {
        int[] nums = {2,3,4,4,5,1};
        System.out.println(findMin(nums));
    }
}
